package 分类.链表;

import java.util.List;

public class 回文链表 {
    public boolean isPalindrome(ListNode head) {
        ListNode slow,fast;
        slow=fast=head;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        if(fast!=null){
            slow=slow.next;
        }
        ListNode left=head;
        ListNode right=reverse(slow);
        while (right!=null){
            if(left.val==right.val){
                left=left.next;
                right=right.next;
            }else {
                return false;
            }
        }
        return true;
    }

    ListNode reverse(ListNode head){
        ListNode cur,pre,nxt;
        pre=null;
        cur=head;

        while (cur!=null){
            nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
}
